
//658.找到K个最接近的元素
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        //先使用二分找到最接近x的两个位置，再使用相向双指针
        int n=arr.size();
        int left=lower_bound(arr.begin(),arr.end(),x)-arr.begin();
        int right=upper_bound(arr.begin(),arr.end(),x)-arr.begin();
        if(right-left-1>=k) return vector<int>(k,x);   //当中间与x相同元素>k时直接返回即可
        while(right<n&&left>=0&&right-left-1<k)
        {
            if(x-arr[left]<=arr[right]-x) left--;
            else right++;
        }
        while(right-left-1<k&&right<n) right++;
        while(right-left-1<k&&left>=0) left--;

        return vector<int>(arr.begin()+left+1,arr.begin()+right);
    }
};